#include<stdio.h>
#define ll long long
#define pr printf
#define sc scanf
#define N 1000005
int prime[N];
int btf_pr[N];
int book[N],b[N];
int l,r;
int main()
{
	int t,k,num,i=1,j=1,cnt=1,count=0,temp=0;
	book[0]=book[1]=1;

	for(num=2;num<=N;num++)
	{
		if(!book[num])
			prime[cnt++]=num;
		for(i=1,j=num*prime[i] ; prime[i]!=0 && j<=N ; i++,j=num*prime[i])
			book[j]=1;
	}
	j=1;
	for(i=1;i<cnt;i++)
	{
		t=0;temp=prime[i];
		while(temp)
		{
			t+=temp%10;
			temp/=10;
		}
		if(!book[t])
			btf_pr[j++]=prime[i];
	}
	j=1;k=1;
	for(i=1;i<=N;i++)
	{
		if(btf_pr[j]==i)
		{
			b[i]=k++;
			j++;
		}
		else b[i]=b[i-1];
	}
	
	sc("%d",&t);getchar();
	for(k=1;k<=t;k++)
	{
		scanf("%d%d",&l,&r);
		pr("Case #%d: %d\n",k,b[r]-b[l-1]);
	}
	return 0;
}

